// 移掉K位数字： https://leetcode-cn.com/problems/remove-k-digits/
package greedy

import (
	"strings"
)

// 这是字节9月6日，一面的试题

// 贪心加 单调栈
// 维护递增栈， 当出现 i < i - 1 位置的时候，就进行删除操作
// 要说贪心的话， 就是优先从高位进行删除，因为高位的数字决定整个数字的大小
// 高位数字越小，整个数字就越小
func removeKdigits(num string, k int) string {
	stack := make([]byte, 0)
	var i int
	// 0. 首先：遍历到最后位置，或者k为0，都不再进行循环
	for i = 0; i < len(num) && k > 0; i++ {
		// 1. 空栈 或者递增 直接插入元素
		// ！ 这里要注意一个问题，前导0的问题，不能将0往空栈中插入
		if (len(stack) == 0 || num[i-1] < num[i]) &&
			num[i] != '0' {
			stack = append(stack, num[i])
			continue
		}
		// 2. 不满足递增，删除元素
		for len(stack) > 0 && stack[len(stack)-1] > num[i] && k > 0 {
			stack = stack[:len(stack)-1]
			k--
		}
		// 3. 当前元素入栈, 如果栈为空，当前元素为 0（形成前导0了），不能入栈,否则都入栈
		if len(stack) == 0 && num[i] == '0' {
			continue
		}
		stack = append(stack, num[i])
	}
	// 4. 最后要判断，如果整个数字都是递增的， k 还没为 0, 那就接着删除（整个数字都到栈中了，直接从栈顶删除）
	// 针对 10 k = 2 的情况，需要全删, 栈为空，再进行 stack[:len(stack)-1] 下标越界错误，需要判断 len(stack) > 0
	for k > 0 && len(stack) > 0 {
		stack = stack[:len(stack)-1]
		k--
	}
	// 5. 拼接最后的结果
	// 针对 "10001" k = 1 的情况， 剩余字符串可能含有前导 0 了，也要进行判断
	for i < len(num) && num[i] == '0' &&
		len(stack) == 0 {
		i++
	}
	rst := string(stack) + num[i:]
	if rst == "" {
		return "0"
	}
	return rst
}

// 官方题解的思路是一样的， 但是它是将所有的都堆进栈中，删除 k 个之前不满足递减，就删除。
// 最后直接在栈中进行删除 可能存在的前导0， 也不存在字符串拼接的情况。因为字符全部到栈中了
// 思路清晰，写的还是很简约的
func removeKdigits(num string, k int) string {
	stack := []byte{}
	for i := range num {
		digit := num[i]
		for k > 0 && len(stack) > 0 && digit < stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
			k--
		}
		stack = append(stack, digit)
	}
	stack = stack[:len(stack)-k]
	ans := strings.TrimLeft(string(stack), "0")
	if ans == "" {
		ans = "0"
	}
	return ans

}
